#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import os


# 英氏标尺
class EnglishRuler:
    def draw_line(self, tick_length, tick_label=''):
        line = '-' * tick_length
        if tick_label:
            line += tick_label
        print(line)

    def draw_interval(self, center_length):
        if center_length > 0:
            self.draw_interval(center_length - 1)
            self.draw_line(center_length)
            self.draw_interval(center_length - 1)

    def draw_ruler(self, num_inches, major_length):
        self.draw_line(major_length, '0')
        for j in range(1, 1 + num_inches):
            self.draw_interval(major_length - 1)
            self.draw_line(major_length, str(j))


def findfiles(path):
    if os.path.isdir(path):
        for file in os.listdir(path):
            findfiles(os.path.join(path, file))
    else:
        print(path)


# 有序序列二分查找算法
def binary_search(data, target, low, high):
    if low > high:
        return False

    mid = (low + high) // 2
    if target == data[mid]:
        return True

    elif target < data[mid]:
        return binary_search(data, target, low, mid - 1)

    else:
        return binary_search(data, target, mid + 1, high)


# 磁盘使用情况
def disk_usage(path):
    total = os.path.getsize(path)
    if os.path.isdir(path):
        for filename in os.listdir(path):
            childpath = os.path.join(path, filename)
            total += disk_usage(childpath)

    print('{0:<7}'.format(total), path)
    return total


# 斐波那契数列
def bad_fibonacci(n):
    if n <= 1:
        return n
    else:
        print(bad_fibonacci(n - 2) + bad_fibonacci(n - 1))
        return bad_fibonacci(n - 2) + bad_fibonacci(n - 1)


def good_fibonacci(n):
    if n <= 1:
        return (n, 0)
    else:
        (a, b) = good_fibonacci(n - 1)
        return a + b, a


# 线性递归计算序列元素的和
def linear_sum(S, n):
    if n == 0:
        return 0
    else:
        return linear_sum(S, n - 1) + S[n - 1]


# 使用线性递归逆置序列的元素
def reverse(S, start, stop):
    if start < stop:
        S[start], S[stop] = S[stop], S[start]
        reverse(S, start + 1, stop - 1)


# 用于计算幂函数
# 算法复杂度O(n)
def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)


# 使用重复的平方计算幂函数
# 算法复杂度O(logn)，所用内存O(logn)
def power2(x, n):
    if n == 0:
        return 1
    else:
        partial = power(x, n // 2)
        result = partial * partial
        if n % 2 == 1:
            result *= x
        return result


# 二路递归计算一个序列的元素之和
# 空间复杂度O(logn)
# 时间复杂度O(n)
def binary_sum(S, start, stop):
    if start > stop:
        return 0
    elif start == stop - 1:
        return S[start]
    else:
        mid = (start + stop) // 2
        return binary_sum(S, start, mid) + binary_sum(S, mid, stop)


# TODO 多重递归

if __name__ == '__main__':
    # disk_usage("/home/lqz/work/study")
    S = [5, 2, 8, 1, 6, 9, 7]
    reverse(S, 0, 6)
